/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

import org.junit.Test;

/**
 * <p>
 * 链表进行分区 
 * 要求保持原来节点的相对顺序。
 * 输入： 1->4->3->2->5->2 and x = 3, 
 * 返回： 1->2->2->4->3->5.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月20日
 */
public class PartitionList {

    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(0);
        ListNode pivot = new ListNode(x);
        
        ListNode first = dummy;
        ListNode second = pivot;
        ListNode curr = head;
        while(curr!=null){
            //保存下一个节点避免中断
            ListNode next = curr.next;
            if(curr.val<x){
                //放置小于X的节点
                first.next = curr;
                first = curr;
            }else{
                //放置大于等于x的节点
                second.next = curr;
                second = curr;
                second.next = null;
            }
            curr = next;
        }
        //前半部分和后半部分连接起来
        first.next = pivot.next;
        return dummy.next;
    }
    @Test
    public void testParti(){
        ListNode head = new ListNode(4);
        head.next = new ListNode(3);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
        head.next.next.next.next = new ListNode(2);
        head.next.next.next.next.next = new ListNode(5);
        
        ListNode node = partition(head, 3);
        while(node!=null){
            System.out.print(" "+node.val+"\t");
            node = node.next;
        }
    }
}
